/*
package com.gitee.wsl.struct.list

import com.gitee.wsl.ext.base.Comparators
import kotlin.test.Test
import kotlin.test.assertFailsWith
import kotlin.test.assertTrue


class RedBlackTreeTest {
    // Rudimentary tests
    // empty tree
    @Test
    fun shouldCreateEmptyTree() {
        val tree = empty<Int>()
        assertTrue(tree.isEmpty)
        assertThat(tree.size()).isEqualTo(0)
        assertThat(tree.color()).isEqualTo(RedBlackTree.Color.BLACK)
    }

    @Test
    fun shouldFailLeftOfEmpty() {
        assertFailsWith(UnsupportedOperationException::class) {
            empty<Any>().left()
        }
    }

    @Test
    fun shouldFailRightOfEmpty() {
        assertFailsWith(UnsupportedOperationException::class) {
            empty<Any>().right()
        }
    }

    @Test
    fun shouldFailValueOfEmpty() {
        assertFailsWith(NoSuchElementException::class) {
            empty<Any>().value()
        }
    }

    // isEmpty
    @Test
    fun shouldRecognizeEmptyTree() {
        assertThat(empty<Any>().isEmpty).isTrue()
    }

    @Test
    fun shouldRecognizeNonEmptyTree() {
        assertThat(of<Int>(1).isEmpty).isFalse()
    }

    // contains
    @Test
    fun shouldRecognizeContainedElement() {
        assertThat(of<Int>(1, 2, 3).contains(2)).isTrue()
    }

    @Test
    fun shouldRecognizeNonContainedElementOfEmptyTree() {
        assertThat(empty<Int>().contains(1)).isFalse()
    }

    @Test
    fun shouldRecognizeNonContainedElementOfNonEmptyTree() {
        assertThat(of<Int>(1, 2, 3).contains(0)).isFalse()
    }

    // insert
    @Test
    fun shouldInsert_2_1_4_5_9_3_6_7() {
        var tree = empty<Int?>()
        assertThat(tree.toString()).isEqualTo("()")
        assertThat(tree.size()).isEqualTo(0)

        tree = tree.insert(2)
        assertThat(tree.toString()).isEqualTo("(B:2)")
        assertThat(tree.size()).isEqualTo(1)

        tree = tree.insert(1)
        assertThat(tree.toString()).isEqualTo("(B:2 R:1)")
        assertThat(tree.size()).isEqualTo(2)

        tree = tree.insert(4)
        assertThat(tree.toString()).isEqualTo("(B:2 R:1 R:4)")
        assertThat(tree.size()).isEqualTo(3)

        tree = tree.insert(5)
        assertThat(tree.toString()).isEqualTo("(B:4 (B:2 R:1) B:5)")
        assertThat(tree.size()).isEqualTo(4)

        tree = tree.insert(9)
        assertThat(tree.toString()).isEqualTo("(B:4 (B:2 R:1) (B:5 R:9))")
        assertThat(tree.size()).isEqualTo(5)

        tree = tree.insert(3)
        assertThat(tree.toString()).isEqualTo("(B:4 (B:2 R:1 R:3) (B:5 R:9))")
        assertThat(tree.size()).isEqualTo(6)

        tree = tree.insert(6)
        assertThat(tree.toString()).isEqualTo("(B:4 (B:2 R:1 R:3) (R:6 B:5 B:9))")
        assertThat(tree.size()).isEqualTo(7)

        tree = tree.insert(7)
        assertThat(tree.toString()).isEqualTo("(B:4 (B:2 R:1 R:3) (R:6 B:5 (B:9 R:7)))")
        assertThat(tree.size()).isEqualTo(8)
    }

    @Test
    fun shouldInsertNullIntoEmptyTreeBecauseComparatorNotCalled() {
        val actual = empty<Int?>().insert(null)
        val expected = of(null as Int?)
        assertThat(java.util.Collections.areEqual(actual, expected)).isTrue()
    }

    @Test
    fun shouldNotInsertNullTwoTimesIntoEmptyTreeBecauseComparatorCalled() {
        assertFailsWith(NullPointerException::class) {
            empty<Int?>().insert(null).insert(null)
        }
    }

    @Test
    fun shouldInsertNonNullIntoEmptyTree() {
        val actual = empty<Int>().insert(2)
        val expected = of(2)
        assertThat(java.util.Collections.areEqual(actual, expected)).isTrue()
    }

    @Test
    fun shouldReturnTheSameInstanceWhenInsertingAnAlreadyContainedElement() {
        val testee = of(1, 2, 3)
        val actual = testee.insert(2)
        assertThat(java.util.Collections.areEqual(actual, testee)).isTrue()
    }

    // delete
    @Test
    fun shouldDelete_2_from_2_1_4_5_9_3_6_7() {
        val testee = of(2, 1, 4, 5, 9, 3, 6, 7)
        val actual = testee.delete(2)
        assertThat(actual.toString()).isEqualTo("(B:4 (B:3 R:1) (R:6 B:5 (B:9 R:7)))")
        assertThat(actual.size()).isEqualTo(7)
    }

    // difference()
    @Test
    fun shouldSubtractEmptyFromNonEmpty() {
        val t1 = of(3, 5)
        val t2 = empty<Int>()
        val actual = t1.difference(t2)
        assertThat(actual).isEqualTo(t1)
    }

    @Test
    fun shouldSubtractNonEmptyFromEmpty() {
        val t1 = empty<Int>()
        val t2 = of(5, 7)
        val actual = t1.difference(t2)
        assertThat(actual).isEqualTo(t1)
    }

    @Test
    fun shouldSubtractNonEmptyFromNonEmpty() {
        val t1 = of(3, 5)
        val t2 = of(5, 7)
        val actual = t1.difference(t2)
        val expected = of(3)
        assertThat(java.util.Collections.areEqual(actual, expected)).isTrue()
    }

    // intersection()
    @Test
    fun shouldIntersectOnNonEmptyGivenEmpty() {
        val t1 = of(3, 5)
        val t2 = empty<Int>()
        val actual = t1.intersection(t2)
        val expected = empty<Int>()
        assertThat(java.util.Collections.areEqual(actual, expected)).isTrue()
    }

    @Test
    fun shouldIntersectOnEmptyGivenNonEmpty() {
        val t1 = empty<Int>()
        val t2 = of(5, 7)
        val actual = t1.intersection(t2)
        val expected = empty<Int>()
        assertThat(java.util.Collections.areEqual(actual, expected)).isTrue()
    }

    @Test
    fun shouldIntersectOnNonEmptyGivenNonEmpty() {
        val t1 = of(3, 5)
        val t2 = of(5, 7)
        val actual = t1.intersection(t2)
        val expected = of(5)
        assertThat(actual == expected).isTrue()
    }

    @Test
    fun shouldIntersectOnNonEmptyGivenNonEmptyUnbalancedHeightLeft() {
        // Node::mergeGT
        //
        // Trees have
        // - different values
        // - similar to each other left children
        // - and unlike each other right children
        val t1 = of(1, 2, 3, 4, 5, 6, 7, 8, 60, 66, 67)
        val t2 = of(1, 2, 3, 10, 11, 12, 13, 14, 60, 76, 77)
        val actual = t1.intersection(t2)
        val expected = of(1, 2, 3, 60)
        assertThat(java.util.Collections.areEqual(actual, expected)).isTrue()
    }

    @Test
    fun shouldIntersectOnNonEmptyGivenNonEmptyUnbalancedHeightRight() {
        // Node::mergeLT
        //
        // Trees have
        // - different values
        // - unlike each other left children
        // - and similar to each other right children
        val t1 = of(1, 2, 3, 4, 40, 61, 62, 63, 64, 65)
        val t2 = of(2, 7, 8, 9, 50, 61, 62, 63, 64, 65)
        val actual = t1.intersection(t2)
        val expected = of(2, 61, 62, 63, 64, 65)
        assertThat(java.util.Collections.areEqual(actual, expected)).isTrue()
    }

    @Test
    fun shouldIntersectOnNonEmptyGivenNonEmptyBalancedHeightRight() {
        // Node::mergeEQ && isRed(n1.right)
        //
        val t1 = of(-10, -20, -30, -40, -50, 1, 10, 20, 30)
        val t2 = of(-10, -20, -30, -40, -50, 2, 10, 20, 30)
        assertThat(java.util.Collections.areEqual(t1.intersection(t2), t1.delete(1))).isTrue()
    }

    */
/*
     * > let tree1 = fromList [8, 14, 0, 7, 9, 3]
     * > let tree2 = fromList [7, 9, 14, 6, 0, 5, 11, 10, 4, 12, 8, 13]
     * > tree1 `intersection` tree2
     * Node B 2 (Node B 1 (Node R 1 Leaf 0 Leaf) 7 Leaf) 8 (Node B 1 (Node R 1 Leaf 9 Leaf) 14 Leaf)
     * > printSet (tree1 `intersection` tree2)
     * B 8 (2)
     * + B 7 (1)
     *   + R 0 (1)
     *     +
     *     +
     *   +
     * + B 14 (1)
     *   + R 9 (1)
     *     +
     *     +
     *   +
     *//*

    @Test
    fun shouldPassIntersectionRegression1_Issue2098() {
        val tree1 = of(8, 14, 0, 7, 9, 3)
        val tree2 = of(7, 9, 14, 6, 0, 5, 11, 10, 4, 12, 8, 13)
        val actual = tree1.intersection(tree2).toString()
        val expected = "(B:8 (B:7 R:0) (B:14 R:9))"
        assertThat(actual).isEqualTo(expected)
    }

    */
/*
     * > let tree1 = fromList [8, 14, 0, 7, 9, 3]
     * > let tree2 = fromList [7, 9, 14, 6, 0, 5, 11, 10, 4, 12, 8, 13]
     * > let tree3 = fromList [1, 2]
     * > (tree1 `intersection` tree2) `intersection` tree3
     * Leaf
     * > tree1 `intersection` (tree2 `intersection` tree3)
     * Leaf
     *//*

    @Test
    fun shouldPassIntersectionRegression2_Issue2098() {
        val tree1 = of(8, 14, 0, 7, 9, 3)
        val tree2 = of(7, 9, 14, 6, 0, 5, 11, 10, 4, 12, 8, 13)
        val tree3 = of(1, 2)
        val actual = tree1.intersection(tree2).intersection(tree3)
        val expected = tree1.intersection(tree2.intersection(tree3))
        assertThat(java.util.Collections.areEqual(actual, expected)).isTrue()
    }

    */
/*
     * > let tree1 = [1462193440, 0, 2147483647, -2147483648, 0, 637669539, -1612766076, -1, 1795938819, 1, 0, -420800448, -2147483648, 497885405, 0, 1084073832, 1, 1439964148, 1961646330]
     * > let tree2 = [-1, 1, 2147483647, -1434983536, -2147483648, -1452486079, 1365799971, 231691980, -1780534767, -2147483648, 1448658704, 0, 1526591298]
     * > tree1 `intersection` tree2
     * Node B 2 (Node B 1 (Node R 1 Leaf (-2147483648) Leaf) (-1) Leaf) 0 (Node B 1 (Node R 1 Leaf 1 Leaf) 2147483647 Leaf)
     *//*

    @Test
    fun shouldPassIntersectionRegression3_Issue2098() {
        val tree1 = of(
            1462193440,
            0,
            2147483647,
            -2147483648,
            0,
            637669539,
            -1612766076,
            -1,
            1795938819,
            1,
            0,
            -420800448,
            -2147483648,
            497885405,
            0,
            1084073832,
            1,
            1439964148,
            1961646330
        )
        val tree2 = of(
            -1,
            1,
            2147483647,
            -1434983536,
            -2147483648,
            -1452486079,
            1365799971,
            231691980,
            -1780534767,
            -2147483648,
            1448658704,
            0,
            1526591298
        )
        val actual = tree1.intersection(tree2).toString()
        val expected = "(B:0 (B:-1 R:-2147483648) (B:2147483647 R:1))"
        assertThat(actual).isEqualTo(expected)
    }

    // union()
    @Test
    fun shouldUnionOnNonEmptyGivenEmpty() {
        val t1 = of(3, 5)
        val t2 = empty<Int>()
        val actual = t1.union(t2)
        val expected = of(3, 5)
        assertThat(java.util.Collections.areEqual(actual, expected)).isTrue()
    }

    @Test
    fun shouldUnionOnEmptyGivenNonEmpty() {
        val t1 = empty<Int>()
        val t2 = of(5, 7)
        val actual = t1.union(t2)
        val expected = of(5, 7)
        assertThat(java.util.Collections.areEqual(actual, expected)).isTrue()
    }

    @Test
    fun shouldUnionOnNonEmptyGivenNonEmpty() {
        val t1 = of(3, 5)
        val t2 = of(5, 7)
        val actual = t1.union(t2)
        val expected = of(3, 5, 7)
        assertThat(java.util.Collections.areEqual(actual, expected)).isTrue()
    }

    @Test
    fun shouldComputeUnionAndEqualTreesOfDifferentShapeButSameElements() {
        val t1 = of(-1, -1, 0, 1)
        val t2 = of(-2, -1, 0, 1)
        val actual = t1.union(t2)
        val expected = of(-2, -1, 0, 1)
        assertThat(java.util.Collections.areEqual(actual, expected)).isTrue()
    }

    // iterator()
    @Test
    fun shouldIterateEmptyTree() {
        assertThat(empty<Any>().iterator().hasNext()).isFalse()
    }

    @Test
    fun shouldIterateNonEmptyTree() {
        val testee = of(7, 1, 6, 2, 5, 3, 4)
        val actual = testee.iterator()
        assertThat(actual.toString()).isEqualTo("List(1, 2, 3, 4, 5, 6, 7)")
    }

    companion object {
        private fun <T> empty(): RedBlackTree<T> {
            return RedBlackTree.empty(Comparators.)
        }

        private fun <T> of(value: T): RedBlackTree<T> {
            return RedBlackTree.of(Comparators.naturalComparator(), value)
        }

        @SafeVarargs
        private fun <T> of(vararg values: T): RedBlackTree<T> {
            return RedBlackTree.< T > of < T ? > (Comparators.naturalComparator(), values)
        }
    }
}
*/
